#include "headfiles.h"

static int compare_string(char *str1, char *str2) {
    char *c1 = strchr(str1, ':');
    char *c2 = strchr(str2, ':');

    if (c1) {
        *c1 = '\0';
    }

    if (c2) {
        *c2 = '\0';
    }

    int res = strcmp(str1, str2);

    if (c1) {
        *c1 = ':';
    }

    if (c2) {
        *c2 = ':';
    }

    return res;
}

static int findEntry(char **input, size_t size, char *root) {
    size_t l, r, index;
    l = 0;
    r = size - 1;

    while (l <= r) {
        index = (l + r) / 2;
        int res = compare_string(input[index], root);
        if (res == 0) {
            return index;
        }
        else if (res < 0) {
            l = index + 1;
        }
        else {
            r = index - 1;
        }
    }

    return -1;
}

static void stringQuickSortRecur(char **input, size_t start, size_t end) {
    if (input == NULL) {
        return;
    }

    if (start >= end) {
        return;
    }

    int pivot_loc = (start + end) / 2;
    char *pivot_str = input[pivot_loc];
    input[pivot_loc] = input[start];

    int index = start;
    int l = index + 1;
    int r = end - 1;

    while (l <= r) {
        int res = compare_string(input[l], pivot_str);
        if (res <= 0) {
            input[index] = input[l];
            ++l;
            ++index;
        }
        else {
            char *tmp_str = input[r];
            input[r] = input[l];
            input[l] = tmp_str;
            r--;
        }
    }

    input[index] = pivot_str;
    stringQuickSortRecur(input, start, index);
    stringQuickSortRecur(input, index + 1, end);

    return;
}

static void stringQuickSort(char **input, size_t size) {
    stringQuickSortRecur(input, 0, size);
}

bool addNeighborList(char **&output,
                     char *neighbor_list,
                     size_t &array_size, 
                     size_t &output_size) {
    if (output_size >= array_size) {
        char **tmp_output = (char **)malloc(sizeof(char *) * array_size * 2);
        memcpy(tmp_output, output, sizeof(char *) * array_size);
        free(output);
        output = tmp_output;
    }

    output[output_size] = strdup(neighbor_list);
    output_size++;

    return true;
}

static bool graphTraverseRecur(char **input, 
                               size_t input_size, 
                               char *root,
                               entry_t **hash_table,
                               size_t table_size,
                               char **&output,
                               size_t &array_size,
                               size_t &output_size) {
    //char neighbor_list[2000000];
    char *neighbor_list = (char *)malloc(sizeof(char) * 2000000);
    memset(neighbor_list, 0, sizeof(char) * 2000000);
    size_t n_loc = 0;

    int index = findEntry(input, input_size, root);
    if (index == -1) {
        return true;
    }


    char *loc, *pre_loc;
    loc = strchr(input[index], ':');
    pre_loc = loc + 1;
    loc = strchr(pre_loc, ',');
    while (loc) {
        size_t size = loc - pre_loc + 1;
        char *one_neighbor = (char *)malloc(size);
        if (one_neighbor == NULL) {
            return NULL;
        }

        memcpy(one_neighbor, pre_loc, size);
        one_neighbor[size - 1] = '\0';

        // check whether the neighbor is already traversed
        bool val;
        bool res = hashtable_getvalue(hash_table, table_size, one_neighbor, val);
        // not hit yet, add to output list
        if (!res) {
            res = hashtable_insert(hash_table, table_size, one_neighbor, true);
            strcpy(&neighbor_list[n_loc], one_neighbor);
            neighbor_list[n_loc + size - 1] = ',';
            n_loc += size;
        }
        free(one_neighbor);

        pre_loc = loc + 1;
        loc = strchr(pre_loc, ',');
    }

    // process the last neighbor
    bool val, res;
    res = hashtable_getvalue(hash_table, table_size, pre_loc, val);
    if (!res) {
        strcpy(&neighbor_list[n_loc], pre_loc);
    }
    else {
        neighbor_list[n_loc - 1] = '\0';
    }

    // Add neighbor_list to the output
    addNeighborList(output, neighbor_list, array_size, output_size);

    // process each neighbor
    pre_loc = neighbor_list;
 
    // if no neighbor is found
    if (*pre_loc == '\0') {
        return output;
    }

   loc = strchr(pre_loc, ',');
    while (loc) {
        size_t size = loc - pre_loc + 1;
        char *one_neighbor = (char *)malloc(size);
        if (one_neighbor == NULL) {
            return NULL;
        }
        memcpy(one_neighbor, pre_loc, size);
        one_neighbor[size - 1] = '\0';

        // Search its neighbor
        graphTraverseRecur(input, input_size, 
                           one_neighbor, hash_table, table_size, 
                           output, array_size, output_size);
        free(one_neighbor);

        pre_loc = loc + 1;
        loc = strchr(pre_loc, ',');
    }

    graphTraverseRecur(input, input_size, pre_loc, 
                       hash_table, table_size,
                       output, array_size, output_size);

    free(neighbor_list);

    return true;
}

char **graphTraverseC(char **input, size_t input_size, size_t *output_size) {
    size_t array_size = 1000;
    char **output = (char **)malloc(sizeof(char *) * array_size);
    if (output == NULL) {
        return NULL;
    }

    entry_t **hash_table = hashtable_create(1000);
    if (hash_table == NULL) {
        return NULL;
    }

    stringQuickSort(input, input_size - 1);

    char *root = input[input_size - 1];
    *output_size = 0;

    hashtable_insert(hash_table, array_size, root, true);

    graphTraverseRecur(input, input_size - 1, root, 
                       hash_table, array_size, 
                       output, array_size, *output_size);

    return output;
}

